/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package com.minidota.utils;

/**
 *
 * @author romanupgrate
 */
import java.util.*;
import java.io.*;

public class Dijkstra {

    public static void dijkstra(Graph g, int s, long[] prio, int[] pred) {
        Arrays.fill(pred, -1);
        Arrays.fill(prio, INF);
        prio[s] = 0;
        Queue<QItem> q = new PriorityQueue<QItem>();
        q.add(new QItem(0, s));
        while (!q.isEmpty()) {
            QItem cur = q.poll();
            if (cur.prio != prio[cur.v]) {
                continue;
            }

            for (Edge e : g.nodeEdges[cur.v]) {
                long nprio = prio[cur.v] + e.cost;
                if (prio[e.t] > nprio) {
                    prio[e.t] = nprio;
                    pred[e.t] = cur.v;
                    q.add(new QItem(nprio, e.t));
                }
            }
        }
    }
    public static final long INF = Long.MAX_VALUE / 10;

    public static class QItem implements Comparable<QItem> {

        long prio;
        int v;

        public QItem(long prio, int v) {
            this.prio = prio;
            this.v = v;
        }

        public int compareTo(QItem q) {
            return prio < q.prio ? -1 : prio > q.prio ? 1 : 0;
        }
    }

    public static class Edge {

        public int s, t, cost;

        public Edge(int s, int t, int cost) {
            this.s = s;
            this.t = t;
            this.cost = cost;
        }
    }

    public static class Graph {

        public final int n;
        public List<Edge>[] nodeEdges;

        public Graph(int n) {
            this.n = n; //конструктор
            nodeEdges = new List[n];
            for (int i = 0; i < n; i++) {
                nodeEdges[i] = new ArrayList<Edge>();
            }
        }

        void addEdge(int s, int t, int cost) {
            nodeEdges[s].add(new Edge(s, t, cost));
        }
    }

    public static ArrayList<Integer> getPath(int arr[][], int start, int end) {

        int n = arr.length;
        Graph g = new Graph(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (arr[i][j] != 0) {
                    g.addEdge(i, j, arr[i][j]);
                }
            }
        }
        long[] path = new long[g.n];
        int[] pred = new int[g.n];
        dijkstra(g, start, path, pred);

        return getPath(pred, end);
    }

    public static ArrayList<Integer> getPath(int[] map, int point) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        while (true) {
            res.add(0, point);
            point = map[point];
            if (point < 0) {
                break;
            }
        }
        return res;
    }
}